{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Number of Vowels in a Substring of Given Length"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #sliding-window"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #滑动窗口"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxVowels"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #定长子串中元音的最大数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你字符串 <code>s</code> 和整数 <code>k</code> 。</p>\n",
    "\n",
    "<p>请返回字符串 <code>s</code> 中长度为 <code>k</code> 的单个子字符串中可能包含的最大元音字母数。</p>\n",
    "\n",
    "<p>英文中的 <strong>元音字母 </strong>为（<code>a</code>, <code>e</code>, <code>i</code>, <code>o</code>, <code>u</code>）。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;abciiidef&quot;, k = 3\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>子字符串 &quot;iii&quot; 包含 3 个元音字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;aeiou&quot;, k = 2\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>任意长度为 2 的子字符串都包含 2 个元音字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;leetcode&quot;, k = 3\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>&quot;lee&quot;、&quot;eet&quot; 和 &quot;ode&quot; 都包含 2 个元音字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;rhythms&quot;, k = 4\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>字符串 s 中不含任何元音字母。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>s = &quot;tryhard&quot;, k = 4\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 10^5</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "\t<li><code>1 &lt;= k &lt;= s.length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-number-of-vowels-in-a-substring-of-given-length](https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-number-of-vowels-in-a-substring-of-given-length](https://leetcode.cn/problems/maximum-number-of-vowels-in-a-substring-of-given-length/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abciiidef\"\\n3', '\"aeiou\"\\n2', '\"leetcode\"\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        cnt = 0\n",
    "        for i in range(n):\n",
    "            if s[i] in \"aeiou\":\n",
    "                cnt+=1\n",
    "            if i-k>=0 and s[i-k] in \"aeiou\":\n",
    "                cnt-=1\n",
    "            ans = max(ans,cnt)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        need = 'aeiou'\n",
    "        left, right = 0, 0\n",
    "        count = 0\n",
    "        ans = 0\n",
    "\n",
    "        while right < len(s):\n",
    "            te1 = s[right]\n",
    "            right += 1\n",
    "            if te1 in need:\n",
    "                count += 1\n",
    "            while right - left > k:\n",
    "                te2 = s[left]\n",
    "                left += 1\n",
    "                if te2 in need:\n",
    "                    count -= 1\n",
    "            ans = max(ans, count)\n",
    "        return ans\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        res = cur = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in 'aeiou':\n",
    "                cur += 1\n",
    "            if i >= k:\n",
    "                cur -= s[i-k] in 'aeiou'\n",
    "            res = max (res,cur)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        left, right = 0, 0\n",
    "        nums, n, max_nums = 0, len(s), 0\n",
    "        vowels = set(list('aeiou'))\n",
    "        while right < n:\n",
    "            if s[right] in vowels:\n",
    "                nums += 1\n",
    "            k -= 1\n",
    "            if k < 0:\n",
    "                if s[left] in vowels:\n",
    "                    nums -= 1\n",
    "                left += 1\n",
    "            right += 1\n",
    "            max_nums = max(max_nums, nums)\n",
    "        return max_nums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        result = cur = sum(c in 'aeiou' for c in s[:k])\n",
    "        for i in range(k, len(s)):\n",
    "            cur += (s[i] in 'aeiou') - (s[i-k] in 'aeiou')\n",
    "            result = max(cur, result)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        tmp={'a','e','i','o','u'}\n",
    "        queue=[]\n",
    "        count=0\n",
    "        res=0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] in tmp:\n",
    "                count+=1\n",
    "            queue.append(s[i])\n",
    "            if len(queue)==k+1:\n",
    "                cur=queue.pop(0)\n",
    "                if cur in tmp:\n",
    "                    count-=1\n",
    "            res=max(res,count)\n",
    "        return res\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        rec = len([i for i in s[:k] if i in [\"a\",\"e\",\"i\",\"o\",\"u\"]])\n",
    "        if len(s) <= k:\n",
    "            return rec\n",
    "        res = rec\n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            if s[i-1] in [\"a\",\"e\",\"i\",\"o\",\"u\"]:\n",
    "                rec -= 1\n",
    "            if s[i + k - 1] in [\"a\",\"e\",\"i\",\"o\",\"u\"]:\n",
    "                rec += 1\n",
    "            res = max(rec, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        sy = [\"a\", \"e\", \"i\", \"o\", \"u\"]\n",
    "        res = 0\n",
    "        count = 0\n",
    "        l, r = 0, k\n",
    "        for i in s[l:r]:\n",
    "            if i in sy:\n",
    "                count += 1\n",
    "        res = count\n",
    "        while r < len(s):\n",
    "            if s[r] in sy:\n",
    "                count += 1\n",
    "            if s[l] in sy:\n",
    "                count -= 1\n",
    "            res = max(res, count)\n",
    "            r += 1\n",
    "            l += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        vowels = ['a','e','i','o','u']\n",
    "        \n",
    "        res = 0 \n",
    "        for i in range(0, min(k, len(s))):\n",
    "            if s[i] in vowels:\n",
    "                res += 1\n",
    "        if len(s) <= k:\n",
    "            return res\n",
    "        temp = res\n",
    "        l = 1\n",
    "        r = k\n",
    "        while r < len(s):\n",
    "            if s[l-1] in vowels: #在下一个窗口中要移除的\n",
    "                temp -= 1\n",
    "            if s[r] in vowels: #在下一个窗口中要增加的\n",
    "                temp += 1\n",
    "            res = max(res, temp)\n",
    "            l += 1\n",
    "            r += 1\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        vowel = 'aeiou'\n",
    "        n = len(s)\n",
    "        cnt = 0\n",
    "        for c in s[:k]:\n",
    "            if c in vowel:\n",
    "                cnt += 1\n",
    "        ma = cnt\n",
    "        i = 0\n",
    "        while i<n-k:  # 长度减长度\n",
    "            e = i+k\n",
    "            if s[i] in vowel:\n",
    "                if s[e] in vowel:\n",
    "                    pass\n",
    "                else:\n",
    "                    cnt -= 1\n",
    "            else:\n",
    "                if s[e] in vowel:\n",
    "                    cnt += 1\n",
    "                else:\n",
    "                    pass\n",
    "            if cnt > ma:\n",
    "                ma = cnt\n",
    "                if ma == k:\n",
    "                    return k\n",
    "            i += 1\n",
    "        return ma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(k):\n",
    "            if s[i] in \"aeiou\":\n",
    "                count += 1\n",
    "\n",
    "        max = count\n",
    "\n",
    "        i = 1\n",
    "        j = k\n",
    "        while j < len(s):\n",
    "            if s[i-1] in \"aeiou\":\n",
    "                count -= 1\n",
    "            if s[j] in \"aeiou\":\n",
    "                count += 1\n",
    "            if max < count:\n",
    "                max = count\n",
    "            i += 1\n",
    "            j += 1\n",
    "\n",
    "        return max"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        vowels = {'a', 'e', 'i', 'o', 'u'}\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            if s[i] in vowels:\n",
    "                cnt += 1\n",
    "        res = cnt\n",
    "\n",
    "        for i in range(k, len(s)):\n",
    "            if s[i - k] in vowels:\n",
    "                cnt -= 1\n",
    "            if s[i] in vowels:\n",
    "                cnt += 1\n",
    "                res = max(res, cnt)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        m = 0 \n",
    "        if n < k:\n",
    "            for p in range(n):\n",
    "                if s[p] in {'a','e','i','o','u'}:\n",
    "                    m+=1 \n",
    "            return m \n",
    "        for p in range(k):\n",
    "            if s[p] in {'a','e','i','o','u'}:\n",
    "                m+=1 \n",
    "        res = m \n",
    "        for i in range(1,n-k+1):\n",
    "            print(m)\n",
    "            if s[i-1] not in {'a','e','i','o','u'} and s[i+k-1] in {'a','e','i','o','u'}:\n",
    "                m += 1 \n",
    "            elif s[i-1] in {'a','e','i','o','u'} and s[i+k-1] not in {'a','e','i','o','u'}:\n",
    "                m -= 1\n",
    "            res = max(res,m)\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        sub = s[:k]\n",
    "        ref = ['a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U']\n",
    "        cur_count = max_count = 0\n",
    "        for j in sub:\n",
    "            if j in ref:\n",
    "                cur_count += 1\n",
    "        max_count = max(cur_count, max_count)\n",
    "        n = len(s)\n",
    "        for i in range(k, n):\n",
    "            if s[i-k] in ref:\n",
    "                cur_count -= 1 \n",
    "            if s[i] in ref:\n",
    "                cur_count += 1 \n",
    "            max_count = max(cur_count, max_count)\n",
    "        return max_count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        if not s:\n",
    "            return 0\n",
    "        vowels = {'a','e','i','o','u'}\n",
    "        cnt = 0\n",
    "        for i in range(k):\n",
    "            if s[i] in vowels:\n",
    "                cnt += 1\n",
    "        res = cnt\n",
    "\n",
    "        for i in range(k, len(s)):\n",
    "            if s[i-k] in vowels:\n",
    "                cnt -= 1\n",
    "            if s[i] in vowels:\n",
    "                cnt += 1\n",
    "                res = max(res, cnt)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        def isVowel(l):\n",
    "            return int(l in \"aeiou\")  \n",
    "\n",
    "        res = count = sum(1 for i in range(k) if isVowel(s[i]))\n",
    "        for i in range(k, len(s)):\n",
    "            count = count - isVowel(s[i-k]) + isVowel(s[i])\n",
    "            res = max(res, count)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        def isVowel(ch):\n",
    "            return int(ch in \"aeiou\")\n",
    "\n",
    "        n = len(s)\n",
    "        start = 0\n",
    "        end = k\n",
    "        vowelsCount = sum(1 for i in range(k) if isVowel(s[i]))\n",
    "        ans = vowelsCount\n",
    "         \n",
    "        while end < n:\n",
    "            vowelsCount += isVowel(s[end])\n",
    "            vowelsCount -= isVowel(s[start])\n",
    "            start += 1\n",
    "            end += 1\n",
    "            ans = max(ans,vowelsCount)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        vowel = 'aeiou'\n",
    "        seq = s[:k]\n",
    "        cnt = 0\n",
    "        # max_cnt = 0\n",
    "        for alpha in seq:\n",
    "            if alpha in vowel:\n",
    "                cnt += 1\n",
    "        print(cnt)\n",
    "        max_cnt = cnt\n",
    "        \n",
    "        for i in range(1, len(s) - k + 1):\n",
    "            if s[i - 1] in vowel:\n",
    "                cnt -= 1\n",
    "            if s[i + k -1] in vowel:\n",
    "                cnt += 1\n",
    "            print(cnt)\n",
    "            if max_cnt < cnt:\n",
    "                max_cnt = cnt\n",
    "        \n",
    "        return max_cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s, k):\n",
    "        vowel_tuple = ('a', 'e', 'i', 'o', 'u')\n",
    "        res = []\n",
    "        num = max_num = 0\n",
    "        for item in s:\n",
    "            res.append(item)\n",
    "            if item in vowel_tuple:\n",
    "                num += 1\n",
    "            if len(res) > k:\n",
    "                x = res.pop(0)\n",
    "                if x in vowel_tuple:\n",
    "                    num -= 1\n",
    "            if num >= max_num:\n",
    "                max_num = num\n",
    "        return max_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        n = len(s)\n",
    "        chars = list(s)\n",
    "\n",
    "        for i in range(n):\n",
    "            if chars[i] in ('a','e','i','o','u'):\n",
    "                chars[i] = '#'\n",
    "        \n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        left = 0\n",
    "        right = min(n-1,k-1)\n",
    "\n",
    "        for i in range(right+1):\n",
    "            if chars[i] == \"#\":\n",
    "                cnt += 1\n",
    "        \n",
    "        res = cnt\n",
    "\n",
    "        while right < n:\n",
    "            if chars[left] == \"#\":\n",
    "                cnt -= 1\n",
    "            \n",
    "            left += 1\n",
    "            right += 1\n",
    "            \n",
    "            if right<n and chars[right] == \"#\":\n",
    "                cnt += 1\n",
    "            \n",
    "            if cnt == k:\n",
    "                return k\n",
    "                           \n",
    "            res = max(res,cnt)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        res = 0\n",
    "        maxres = float('-inf')\n",
    "        lent = len(s)\n",
    "        mystr = ['a','e','i','o','u']\n",
    "        temp = []\n",
    "        for i in range(lent):\n",
    "            if i<k:\n",
    "                if s[i] in mystr:\n",
    "                    res+=1\n",
    "                temp.append(s[i])\n",
    "                # maxres = max(maxres,res)\n",
    "            else:\n",
    "                if s[i] in mystr:\n",
    "                    res+=1\n",
    "                temp.append(s[i])\n",
    "                if temp[0] in mystr:\n",
    "                    res-=1\n",
    "                del temp[0]\n",
    "            maxres = max(maxres,res)\n",
    "        return maxres\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxVowels(self, s: str, k: int) -> int:\n",
    "        s2 = [1 if  c in \"aeiou\" else 0 for c in s.lower() ]\n",
    "        if len(s2)<=k: return sum(s2)\n",
    "\n",
    "        max_cnt = cur_cnt = sum(s2[:k])\n",
    "        for i in range(k, len(s)):\n",
    "            if s2[i]: cur_cnt +=1\n",
    "            if s2[i-k]: cur_cnt -=1\n",
    "            max_cnt = max(max_cnt, cur_cnt)\n",
    "        return max_cnt\n",
    "        \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
